export const getInputs = () => [['(()'], [')()())'], ['']];

/**
 * **[32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses/)**
 *
 * 给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * @param s
 * @returns
 */
export default function longestValidParentheses(s: string): number {
	const len = s.length;
	const dp = new Array(len).fill(0);
	let maxLen = 0;

	for (let i = 1; i < len; i++) {
		if (s[i] === ')') {
			if (s[i - 1] === '(') {
				dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
			} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
				dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
			}
			maxLen = Math.max(maxLen, dp[i]);
		}
	}

	return maxLen;
}
